package com.feonix.algorithm.getcontinuousstring;

import java.util.regex.Pattern;

/**
 * 
 * 读入一个字符串str，输出字符串str中的连续最长的数字串 输入描述:
 * 
 * 测试输入包含1个测试用例，一个字符串str，长度不超过255。 输出描述:
 * 
 * 在一行内输出str中里连续最长的数字串。 输入例子:
 * 
 * abcd12345ed125ss123456789 输出例子:
 * 
 * 123456789
 * 
 * 动态规划。每个位置维护一个f[i]，初始化为0，表示以i点结尾的最长数字串长度。如果位置i为数字，则f[i]=
 * f[i-1]+1，否则，f[i]=0。同时维护一个a[i]，表示以i结尾的最长数字串开始位置。扫描一遍时记录更新最大f[i]，及其对应的a[i]。最后输出即可。
 * 时间复杂度O(n)
 * 
 * @author Administrator
 */
public class ContinuousString {

	private static final String REGEX = "^\\d$";

	/**
	 * 动态规划
	 * 
	 * @param str
	 * @return
	 */
	public static String getContinuousStringByDP(final String str) {
		char[] tempStr = str.toCharArray();
		Pattern pattern = Pattern.compile(REGEX);
		int[] indexTmp = new int[tempStr.length];
		int maxCount = 0;
		int maxIndex = 0;
		for (int i = 0; i < tempStr.length; i++) {
			if (pattern.matcher(tempStr[i] + "").matches()) {
				if (i == 0) {
					indexTmp[i] = 1;
					maxCount = 1;
					maxIndex = 1;
				} else {
					indexTmp[i] = indexTmp[i - 1] + 1;
					if (maxCount <= indexTmp[i]) {
						maxCount = indexTmp[i];
						maxIndex = i;
					}
				}
			} else {
				indexTmp[i] = 0;
			}
		}
		System.out.println(maxIndex);
		System.out.println(maxCount);
		return str.substring(maxIndex - maxCount + 1, maxIndex + 1);
	}

	public static void main(String[] args) {
		String str = "abc1231asdadaeqweqwe2222dasdacxcopopj31231231123dd88888888888888888dd";
		System.out.println(getContinuousStringByDP(str));
	}

}
